package com.cuz.daileetcode.bst;

import java.util.*;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * @author cuzz
 * @version 1.0
 * @description: 二叉搜索树
 * @date 22:08 2022/1/12
 **/
public class BinarySearchTree<K, V> {

    /***
     * 根节点的父节点，方便进行删除操作，可以看作是哑节点，在树中无实际意义
     * 默认当前节点 左节点就是root节点
     */
    private BinarySearchTreeNode<K, V> preNode;
    /**
     * 比较器
     */
    private Comparator<K> keyComparator;

    /***
     * 初始化哑巴节点
     * @param rootNode 根节点 默认哑节点的左孩子指向 当前根节点
     */
    private void initPreNode(BinarySearchTreeNode<K, V> rootNode) {
        this.preNode = BinarySearchTreeNode.<K, V>builder().build();
        this.preNode.setLeft(rootNode);
        this.preNode.setRight(rootNode);
    }

    public static <K, V> BinarySearchTree<K, V> create(BinarySearchTreeNode<K, V> rootNode) {
        BinarySearchTree<K, V> res = new BinarySearchTree<>();

        res.initRootOfThis(rootNode);
        return res;
    }

    public static <K, V> BinarySearchTree<K, V> create(BinarySearchTreeNode<K, V> rootNode, Comparator<K> keyComparator) {
        BinarySearchTree<K, V> res = create(rootNode);
        res.keyComparator = keyComparator;
        return res;
    }

    private BinarySearchTree() {
    }

    /***
     * 判断当前节点的为根的树是否包含我们寻找的key
     * @param key 目标key
     * @param node 当前树的子树是搜索目标
     * @return 是否包含
     */
    public boolean contains(K key, BinarySearchTreeNode<K, V> node) {
        if (Objects.isNull(key)) {
            return false;
        }
        if (Objects.isNull(node)) {
            return false;
        }
        int compareRes = node.compareKey(key, this.keyComparator);
        if (compareRes == 0) {
            return true;
        } else if (compareRes < 0) {
            //当前节点小于key 说明在右树
            return contains(key, node.getRight());
        } else {
            //当前节点大于key 说明在左树
            return contains(key, node.getLeft());
        }
    }

    /***
     * 查看当前整棵树是否包含目标key
     * @param key 搜索的目标key
     * @return 是否包含
     */
    public boolean contains(K key) {
        return contains(key, rootOfThis());
    }

    /***
     * 查找最小的节点
     * @param node 在此节点为根的树上寻找
     * @return 最小的节点信息
     */
    public BinarySearchTreeNode<K, V> findMin(BinarySearchTreeNode<K, V> node) {
        return extreme(node, BinarySearchTreeNode::getLeft);
    }

    /***
     * 查找整树最小的节点
     * @return 最小的节点信息
     */
    public BinarySearchTreeNode<K, V> findMin() {
        return extreme(rootOfThis(), BinarySearchTreeNode::getLeft);
    }

    /***
     * 找最极端的节点
     * 可以最大or 最小
     * @param node 当前节点为根的树上寻找
     * @param recurseWay 如何递归
     * @return 最极端的节点
     */
    private BinarySearchTreeNode<K, V> extreme(BinarySearchTreeNode<K, V> node, Function<BinarySearchTreeNode<K, V>, BinarySearchTreeNode<K, V>> recurseWay) {
        //当前节点为null 那么就是最极端的哪一个
        if (Objects.isNull(node)) {
            return null;
        }
        //如何递归，你可以定义是左树还是右树，递归出口的要求是叶子节点，叶子节点才是最大or最小
        return findByConsumerWay(node, recurseWay, BinarySearchTreeNode::isLeaf);
    }



    /***
     * 自定义查找此树
     * @param node 以此节点作为根去寻找
     * @param recurseWay 如何递归
     * @param requirement 描述你要找节点的特征
     * @return 目标节点
     */
    private BinarySearchTreeNode<K, V> findByConsumerWay(BinarySearchTreeNode<K, V> node, Function<BinarySearchTreeNode<K, V>,
            BinarySearchTreeNode<K, V>> recurseWay, Predicate<BinarySearchTreeNode<K, V>> requirement) {
        //如果根节点 满足要求 那么返回根节点
        if (requirement.test(node)) {
            return node;
        }
        //当前节点为null 那么说明找不到了 不需要继续找了
        if (Objects.isNull(node)) {
            return null;
        }
        //如何递归 获得recurseWay 描述的值
        BinarySearchTreeNode<K, V> recurseValue = recurseWay.apply(node);
        //获取递归的值，使用requirement检测，是否满足返回的要求
        if (requirement.test(recurseValue)) {
            return node;
        }
        //继续找下去
        return findByConsumerWay(recurseValue, recurseWay, requirement);
    }

    /***
     * 查找最大的节点
     * @param node 在此节点为根的树上寻找
     * @return 最小的节点信息
     */
    public BinarySearchTreeNode<K, V> findMax(BinarySearchTreeNode<K, V> node) {
        return extreme(node, BinarySearchTreeNode::getRight);
    }

    /***
     * 查找整颗树最大的节点
     * @return 最小的节点信息
     */
    public BinarySearchTreeNode<K, V> findMax() {
        return extreme(rootOfThis(), BinarySearchTreeNode::getRight);
    }

    /**
     * 获取当前数的根节点 是哑节点的左数
     *
     * @return 数的左节点
     */
    private BinarySearchTreeNode<K, V> rootOfThis() {
        return this.preNode.getLeft();
    }

    /***
     * 初始化当前数的根节点
     * 设置哑节点的左右均为node
     * @param node 期望此节点作为根节点
     */
    private void initRootOfThis(BinarySearchTreeNode<K, V> node) {
        Objects.requireNonNull(node);
        this.preNode = BinarySearchTreeNode.<K, V>builder().build();
        this.preNode.setRight(node);
        this.preNode.setLeft(node);
    }

    /***
     * 插入节点
     * 如果当前root为null 那么当前push的值为当前节点
     * 如果当前节点找到合适位置 那么假如到value集合中
     * 如果找到叶子节点也找不到 那么设置为叶子节点的子节点
     * @param key 目标key
     * @param value 目标value
     */
    public void push(K key, V value) {
        Objects.requireNonNull(key);
        BinarySearchTreeNode<K, V> nodeNeedInsert = BinarySearchTreeNode.<K, V>builder()
                .value(value)
                .key(key)
                .build();
        if (Objects.isNull(rootOfThis())) {
            this.initRootOfThis(nodeNeedInsert);
            return;
        }
        BinarySearchTreeNode<K, V> curNodeFather = rootOfThis();
        while (curNodeFather != null) {
            int compareRes = curNodeFather.compareKey(key, this.keyComparator);
            if (compareRes == 0) {
                curNodeFather.add(value);
                return;
            }
            //当前节点是叶子 将当前节点插入到其下方了
            if (curNodeFather.isLeaf()) {
                //当前节点大于目标key 值 so 应该是左子树
                if (compareRes > 0) {
                    curNodeFather.setLeft(nodeNeedInsert);
                } else {
                    //等于上面已经return so 这里只能是 小于0
                    curNodeFather.setRight(nodeNeedInsert);
                }
                return;
            }
            //不是叶子节点 说明 还可以继续
            //当前节点 大于 目标key 向左
            if (compareRes > 0) {
                if (curNodeFather.getLeft() == null) {
                    curNodeFather.setLeft(nodeNeedInsert);
                }
                curNodeFather = curNodeFather.getLeft();
            } else {
                if (curNodeFather.getRight() == null) {
                    curNodeFather.setRight(nodeNeedInsert);
                }
                curNodeFather = curNodeFather.getRight();
            }
        }
    }

    /**
     * 删除目标key
     *
     * @param targetKey 目标key
     */
    public void remove(K targetKey) {
        if (isEmpty()) {
            return;
        }
        BinarySearchTreeNode<K, V> deleteNodePre = this.preNode;
        BinarySearchTreeNode<K, V> nodeMayBeDelete = rootOfThis();
        while (deleteNodePre != null && nodeMayBeDelete != null) {
            //当前节点就是要被删除的节点
            int compareRes = compareKey(nodeMayBeDelete, targetKey);
            if (compareRes == 0) {
                //如果是叶子节点 那么直接删除即可
                if (nodeMayBeDelete.isLeaf()) {
                    removeRelation(deleteNodePre, nodeMayBeDelete);
                } else {
                    //如果删除节点存在右儿子/
                    int leftOfRightFlag = compareKey(deleteNodePre, nodeMayBeDelete.getKey());
                    BinarySearchTreeNode<K, V> deleteLeftSon = nodeMayBeDelete.getLeft();
                    BinarySearchTreeNode<K, V> deleteRightSon = nodeMayBeDelete.getRight();
                    //代替删除节点节点 因为不是叶子节点 其儿子需要顶替它的位置
                    BinarySearchTreeNode<K, V> replaceDeleteNode;
                    //存在一个节点为null
                    if (deleteLeftSon == null || deleteRightSon == null) {
                        //如果删除节点的右儿子不为空 那么我们要用右儿子代替它的位置
                        if (deleteRightSon != null) {
                            replaceDeleteNode = deleteRightSon;
                        } else {
                            //反之用左儿子代替
                            replaceDeleteNode = deleteLeftSon;
                        }
                    } else {
                        //如果存在左树右树都不为空。
                        //我们可以 找左树最大的节点代替它 也可以找 右树最小的节点代替它
                        replaceDeleteNode = findMax(nodeMayBeDelete.getLeft());
                        //继承删除节点的有孩子
                        replaceDeleteNode.setRight(nodeMayBeDelete.getRight());
                    }
                    //代替节点的左等于删除的左，右等于右
                    // 那么让它的儿子代替它
                    if (leftOfRightFlag < 0) {
                        deleteNodePre.setRight(replaceDeleteNode);
                    } else {
                        //当前要删除的节点是右树
                        deleteNodePre.setLeft(replaceDeleteNode);
                    }
                }
                clearNode(nodeMayBeDelete);
                return;
            } else {
                //父节点变为当前节点
                deleteNodePre = nodeMayBeDelete;
                if (compareRes < 0) {
                    //待删除的节点小于当前节点 向右树
                    nodeMayBeDelete = nodeMayBeDelete.getRight();
                } else {
                    //反之向左树 等于0的情况进入上面一个分支了
                    nodeMayBeDelete = nodeMayBeDelete.getLeft();
                }
            }
        }
    }

    /***
     * 清除关系
     * 断绝父子关系 前提是 他们是父子
     * @param father 父节点
     * @param son 子节点
     */
    private void removeRelation(BinarySearchTreeNode<K, V> father, BinarySearchTreeNode<K, V> son) {
        if (father == null) {
            return;
        }
        if (Objects.equals(father.getLeft(), son)) {
            father.setLeft(null);
        } else if (Objects.equals(father.getRight(), son)) {
            father.setRight(null);
        }
    }

    /**
     * 清空左右儿子，方便垃圾回收器回收
     *
     * @param node 当前需要清理的节点
     */
    private void clearNode(BinarySearchTreeNode<K, V> node) {
        if (null == node) {
            return;
        }
        node.setRight(null);
        node.setLeft(null);
    }

    /**
     * 比较当前节点 和key
     * 大于0 返回正数，小于0返回负数
     * 等于返回0
     *
     * @param node 当前节点
     * @param key  比较的key
     * @return 大小关系
     */
    private int compareKey(BinarySearchTreeNode<K, V> node, K key) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(node);
        //当前节点 和 哑节点相同 那么直接返回 1 那么就会去比较左树也就是根节点
        if (node == this.preNode) {
            return 1;
        }
        return node.compareKey(key, this.keyComparator);
    }

    /***
     * 是否是空树
     * @return 返回当前根节点是否为null
     */
    public boolean isEmpty() {
        return Objects.isNull(rootOfThis());
    }

    /***
     * 查找key 对应的节点
     * @param key 目标key
     * @return 可能 存在的和key对应的目标节点
     */
    public Optional<BinarySearchTreeNode<K, V>> findNode(K key) {
        if (key == null) {
            return Optional.empty();
        }
        BinarySearchTreeNode<K, V> findRes = findByConsumerWay(preNode, node -> {
            if (compareKey(node, key) < 0) {
                return node.getRight();
            } else {
                return node.getLeft();
            }
        }, node -> compareKey(node, key) == 0);
        return Optional.ofNullable(findRes);
    }

    /***
     * 获取key对应节点的值
     * @param key 寻找的目标key
     * @return 节点的值
     */
    public List<V> values(K key) {
        return findNode(key)
                .map(BinarySearchTreeNode::getValueList)
                .orElse(Collections.emptyList());
    }

    /**
     * 强制更新
     *
     * @param key    目标key
     * @param values 企图替换成什么
     */
    public void forceUpdate(K key, V... values) {
        findNode(key).ifPresent(
                node -> {
                    LinkedList<V> replace;
                    if (values == null) {
                        replace = new LinkedList<V>();
                    } else {
                        replace = Arrays.stream(values).collect(Collectors.toCollection(LinkedList::new));
                    }
                    node.setValueList(replace);
                }
        );
    }

    /**
     * 强制更新
     *
     * @param key         目标key
     * @param sourceValue 原来的值
     * @param newValue    企图替换成什么
     */
    public void update(K key, V sourceValue, V newValue) {
        findNode(key).ifPresent(node -> {
            List<V> valueList = node.getValueList();
            //原来的值存在 才会替换
            if (valueList.contains(sourceValue)) {
                valueList.remove(sourceValue);
                valueList.add(newValue);
            }
        });
    }
}
